#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<sstream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
class TheLargestString
{
public:
    static const int MAX_LEN = 47;

    string find(string s,string t)
    {
        int n = s.size();
        /**
         *dp[i][j]:largest from 1 to the i have j chars
        */
        pair<string,string> dp[MAX_LEN+2][MAX_LEN+2];
        for(int i=0;i<MAX_LEN+2;i++)for(int j=0;j<MAX_LEN+2;j++) dp[i][j]=make_pair("","");
        for(int j=1;j<=n;j++){
            string r = t.substr(0,j);
            r=string(r.rbegin(),r.rend());
            dp[j][j]=make_pair(s.substr(0,j),r);
            for(int i=j+1;i<=n;++i){
                dp[i][j]=dp[i-1][j];
                dp[i][j]=max(dp[i][j],make_pair(s[i-1]+dp[i-1][j-1].first,dp[i-1][j-1].second+t[i-1]));
            }
        }
        string res = dp[n][0].first+dp[n][0].second;
        for(int j=1;j<=n;j++){
            res=max(res,dp[n][j].first+dp[n][j].second);
        }
        return res;
    }
    string find1(string S,string T)
    {
        int n = S.length();
        pair<string,string> dp[1+MAX_LEN];
        string result="";
        dp[0]=make_pair("","");
        for(int c=1;c<=n;c++) {
            dp[c]=make_pair(string()+S[c-1],string()+T[c-1]);
            for (int j=0;j<c;j++){
                pair<string,string> tmp = make_pair(dp[j].first+S[c-1],T[c-1]+dp[j].second);
                if (dp[c].first+dp[c].second < tmp.first+tmp.second){
                    dp[c]=tmp;
                }
            }
            cout<<dp[c].first+dp[c].second<<endl;
        }
        result=max(result,dp[n].first+dp[n].second);
        return result;
    }
};
int main()
{

    TheLargestString ls;
    cout<<ls.find("ab","zy")<<endl;
    cout<<ls.find("abacaba","zzzaaaa")<<endl;
    cout<<ls.find("x","x")<<endl;
    cout<<ls.find("abbabbabbababaaaabbababab","bababbaabbbababbbbababaab")<<endl;
}
